# 3-7 用Python实现从中序表达式到后序表达式的转换
import string

from pythonds.basic import Stack


def infixToPostfix(infixexpr):
    prec = {'*': 3, "/": 3, "+": 2, "-": 2, "(": 1};  # 符号的权重

    index = 0;
    postfixList = []  # 列表
    opStack = Stack()  # 栈

    while index < len(infixexpr):
        token = infixexpr[index]  # item
        # 字母
        if token in string.ascii_uppercase:
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ")":
            topTocken = opStack.pop();
            while topTocken != '(':
                postfixList.append(topTocken)
                topTocken = opStack.pop()
        elif token in '+-*/':
            while not opStack.isEmpty() and (prec[opStack.peek()] > prec[token]):
                postfixList.append(opStack.pop())
            opStack.push(token)
        index += 1
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    return ''.join(postfixList)


print(infixToPostfix("(A+B)*(C+D)"))
